package code1.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 原题链接：https://leetcode.cn/problems/combination-sum-ii/
 */
public class P40 {

    List<List<Integer>> result=new ArrayList<>();       //返回结果集
    int[] path=new int[31];                             //记录符合要求组合的栈
    int top=0;                                          //栈顶指针
    int sum=0;

    public void backtracking(int[] candidates, int target,int startIndex){
        if(sum>=target){
            if(sum>target) return;
            if(sum==target){
                List<Integer> list=new ArrayList<>();
                for(int i=1;i<=top;i++){
                    list.add(path[i]);
                }
                result.add(list);
                return;
            }
        }
        for(int i=startIndex;i<candidates.length;i++){
            path[++top]=candidates[i];
            sum+=candidates[i];
            backtracking(candidates,target,i+1);
            sum-=candidates[i];                             //回溯
            top--;
            while (i+1<candidates.length && candidates[i]==candidates[i+1] ){
                i++;                                        //若之后的元素与当前元素相同，则会产生相同的组合，因此应当跳过(本题的关键)
            }
        }
    }


    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);                            //排序
        backtracking(candidates,target,0);
        return result;
    }
}
